/*
 * @lc app=leetcode id=446 lang=cpp
 *
 * [446] Arithmetic Slices II - Subsequence
 */

// @lc code=start
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
    
        int n = nums.size();
        long ans = 0;
        unordered_map<int, int> *dp= new unordered_map<int, int>[n];
        for (int i = 0; i < n; ++i) {
            auto &table = dp[i];
            for (int j = 0; j < i ; ++j) {
                long delta = (long)(nums[j]) - (long) (nums[i]);
                if (delta > INT_MAX || delta < INT_MIN) {
                    continue;;
                }
                int diff = (int)delta;
            
                int sum = 0;
                if (dp[j].find(diff) != dp[j].end()) {
                    sum = dp[j][diff];
                } 
                int origin = 0;
                if (dp[i].find(diff) != dp[i].end()) {
                    origin = dp[i][diff];
                }
                dp[i][diff] =  origin + sum + 1;
                ans += sum;
            }
        }
        return ans;
    }
};
// @lc code=end

